package leetcode._06_回溯;

import org.junit.Test;

import java.util.*;

/**
 * @author pppppp
 * @date 2022/3/1 17:40
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * <p>
 * 回文串 是正着读和反着读都一样的字符串。
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 * <p>
 * 输入：s = "a"
 * 输出：[["a"]]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 */
public class _131_分割回文串 {

    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();


    @Test
    public void T_review2() {
        // List<List<String>> lists = partition_review2("cbbbcc");
        List<List<String>> lists = partition_review3("cbbbcc");
        System.out.println();
    }

    /*回溯 + 动态规划*/
    public List<List<String>> partition_review3(String s) {
        int n = s.length();
        boolean[][]f = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], true);
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
            }
        }
        dfs_review3(s, 0,f);
        return res;
    }

    private void dfs_review3(String s, int index, boolean[][] f) {
        if(index == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if(f[index][i]){
                String s1 = s.substring(index, i + 1);
                path.add(s1);
                dfs_review3(s,i+1,f);
                path.removeLast();
            }
        }
    }

    /*别人的优化题解 将所有s[i,j]是否为回文先算出来*/
    public List<List<String>> partition_review2(String s) {
        int len = s.length();
        List<List<String>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        char[] charArray = s.toCharArray();
        // 预处理
        // 状态：dp[i][j] 表示 s[i][j] 是否是回文
        boolean[][] dp = new boolean[len][len];
        // 状态转移方程：在 s[i] == s[j] 的时候，dp[i][j] 参考 dp[i + 1][j - 1]
        for (int right = 0; right < len; right++) {
            // 注意：left <= right 取等号表示 1 个字符的时候也需要判断
            for (int left = 0; left <= right; left++) {
                if (charArray[left] == charArray[right] && (right - left <= 2 || dp[left + 1][right - 1])) {
                    dp[left][right] = true;
                }
            }
        }

        Deque<String> stack = new ArrayDeque<>();
        dfs(s, 0, len, dp, stack, res);
        return res;
    }

    private void dfs(String s, int index, int len, boolean[][] dp, Deque<String> path, List<List<String>> res) {
        if (index == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < len; i++) {
            if (dp[index][i]) {
                path.addLast(s.substring(index, i + 1));
                dfs(s, i + 1, len, dp, path, res);
                path.removeLast();
            }
        }
    }



    @Test
    public void T_review1() {
        List<List<String>> aabaa = partition_review("cbbbcc");
        System.out.println();
    }


    /*review1：空间优化*/
    public List<List<String>> partition_review(String s) {
        char[] chs = s.toCharArray();
        /*数据预处理，将同一字母的所有位置都保存起来便于后续的查找*/
        HashMap<String, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < chs.length; i++) {
            if (map.containsKey(String.valueOf(chs[i]))) {
                List<Integer> indexs = map.get(String.valueOf(chs[i]));
                indexs.add(i);
            } else {
                List<Integer> indexs = new ArrayList<>();
                indexs.add(i);
                map.put(String.valueOf(chs[i]), indexs);
            }
        }
        HashMap<String,  List<List<String>>> sMap = new HashMap<>();
        ArrayList<String> t = new ArrayList<>();
        t.add(String.valueOf(s.charAt(0)));
        List<List<String>> s0 = new ArrayList<>();
        s0.add(t);
        sMap.put(String.valueOf(s.charAt(0)),s0);
        for (int i = 1; i < s.length(); i++) {

            String sCur = String.valueOf(s.charAt(i));
            List<List<String>> pre = sMap.get(s.substring(0, i));
            List<List<String>> cur = new ArrayList<>();
            copyDeep(pre,cur);

            /*新元素与前面所有元素分开*/
            for (List<String> sList : cur) {
                sList.add(sCur);
            }

            /*新元素与前面的元素形成回文串*/
            List<Integer> sIndexs = map.get(sCur);
            for (Integer sIndex : sIndexs) {
                if(sIndex < i){
                    String subS = s.substring(sIndex,i+1);
                    if(isHuiwen(subS)){
                        List<List<String>> p = sMap.get(s.substring(0, sIndex));
                        List<List<String>> t2 = new ArrayList<>();
                        if(p != null){
                            copyDeep(p,t2);
                            for (List<String> sList : t2) {
                                sList.add(subS);
                            }
                        }else {
                            ArrayList<String> list = new ArrayList<>();
                            list.add(subS);
                            t2.add(list);
                        }
                        /*新元素与前面所有元素分开*/
                        cur.addAll(t2);
                    }
                }
            }
            sMap.put(s.substring(0,i+1),cur);
        }
        return sMap.get(s);
    }

    private void copyDeep(List<List<String>> pre, List<List<String>> cur) {
        for (List<String> p : pre) {
            ArrayList<String> t0 = new ArrayList<>();
            t0.addAll(p);
            cur.add(t0);
        }
    }


    private boolean isHuiwen(String subS) {
        int len = subS.length();
        if(len <2){
            return true;
        }
        int l=0,r = len-1;
        while (l <= r){
            if(subS.charAt(l++) != subS.charAt(r--)){
                return false;
            }
        }
        return true;
    }

    @Test
    public void T_() {
        List<List<String>> aabaa = partition("aabaa");
        System.out.println();
    }

    public List<List<String>> partition(String s) {
        if (s.length() == 0) {
            return res;
        }
        dfs(s);
        return res;
    }

    public void dfs(String s) {

        if (s.length() == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            /*temp为第一个回文串*/
            String temp = s.substring(0, i + 1);
            if (isHuiWen(temp)) {
                path.add(temp);
                dfs(s.substring(i + 1));
                path.removeLast();
            }
        }
    }

    private boolean isHuiWen(String sub) {
        if (sub.length() <= 1) {
            return true;
        }
        int l = 0, r = sub.length() - 1;
        while (l < r) {
            if (sub.charAt(l) != sub.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}
